package leetcode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 225.用队列实现栈
 * 请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
 */

/** 双队列实现栈 **/
class MyStack {

    //q1是实际存储元素的队列
    private Queue<Integer> q1 = new LinkedList<>();
    //q2是辅助队列
    private Queue<Integer> q2 = new LinkedList<>();

    public MyStack() {

    }

    public void push(int x) {
        if(q1.isEmpty()){
            q1.offer(x);
        }else{
            //把新增的元素加到q2中
            q2.offer(x);
            //将q1的元素依次弹出，添到q2的后面
            while(!q1.isEmpty()){
                q2.offer(q1.poll());
            }
            //此时实际存储元素的队列是q2
            //交换q1和q2的引用指向
            Queue<Integer> temp = q1;
            q1 = q2;
            q2 = temp;
        }
    }

    public int pop() {
        return q1.poll();
    }

    public int top() {
        return q1.peek();
    }

    public boolean empty() {
        return q1.isEmpty();
    }
}

/** 单队列实现栈 **/
class MyStack2 {

    //q是存储元素的队列
    private Queue<Integer> q = new LinkedList<>();

    public MyStack2() {

    }

    public void push(int x) {
        //直接在尾部添加新的元素
        q.offer(x);
        //把新元素前面的所有元素依次出队再入队
        for(int i=1; i<q.size(); i++){
            q.offer(q.poll());
        }
    }

    public int pop() {
        return q.poll();
    }

    public int top() {
        return q.peek();
    }

    public boolean empty() {
        return q.isEmpty();
    }
}

public class Num_225 {

}
